package com.chapter6;

public class ArrayOperation {

	private int[] arr;
	private int[] A;
	private int[] B;
	
	public void swap(int i,int j){
		int temp=arr[i];
		arr[i]=arr[j];
		arr[j]=temp;
	}
	public void dutchSort(int[] A,int index){
		arr= new int[A.length];
		arr=A;
		int value=arr[index];
		int low=0;
		int mid=0;
		int high=A.length-1;
		while(mid<high){
			if(arr[mid]==value)
				mid++;
			else if(arr[mid]<value){
				swap(mid,low);
				low++;
				mid++;
			}
			else if(arr[mid]>value){
				swap(high,mid);
				high--;
			}
		}
	}
	
	public void quickSortHelper(int[] A){
		
	}
	public int[] bigIntegerAdder(int[] x, int[] y){
		int lengthX=x.length;
		int lengthY=y.length;
		int maxLength = lengthX;
		int minLength=lengthY;
		if(lengthY>lengthX)
		{ 
			maxLength=lengthY;
			minLength=lengthX;
		}
		int [] sum=new int[maxLength+1];
		int carry=0;
		for(int i=0;i<minLength;i++){
			sum[maxLength-i]=carry+y[lengthY-1-i]+x[lengthX-1-i];
			if(sum[maxLength-i]>9){
				carry=1;
				sum[maxLength-i]=sum[maxLength-i]-10;
			}
			else
				carry=0;
		}
		if(lengthX>lengthY){
			for(int i=1;i<=maxLength-minLength;i++)
				{
					sum[maxLength-minLength-i+1]=carry+x[maxLength-minLength-i];
					if(sum[maxLength-minLength-i+1]>9){
						carry=1;
						sum[maxLength-minLength-i+1]=sum[maxLength-minLength-i+1]-10;
					}
					else
						carry=0;
				}
		}
		if(lengthY>lengthX){
			for(int i=1;i<=maxLength-minLength;i++)
				{
					sum[maxLength-minLength-i+1]=carry+y[maxLength-minLength-i];
					if(sum[maxLength-minLength-i+1]>9){
						carry=1;
						sum[maxLength-minLength-i+1]=sum[maxLength-minLength-i+1]-10;
					}
					else
						carry=0;
				}
		}
		
			
		sum[0]=carry;
		for(int i=0;i<sum.length;i++){
			System.out.println(sum[i]);
		}
		return sum;
	}
	public void printArray(){
		for(int i=0;i<arr.length;i++){
			System.out.println(arr[i]);
		}
	}
	
	public String bigIntegerAddition(String x, String y){
		//x and y are positive integers for now
		int lengthX=x.length();
		int lengthY=y.length();
		int maxLength,minLength;
		if(lengthX>lengthY){
			for(int i=0;i<lengthX-lengthY;i++)
				y="0"+y;
			maxLength=lengthX;
			minLength=lengthY;
		}
		else{
			for(int i=0;i<lengthY-lengthX;i++)
				x="0"+x;
			maxLength=lengthY;
			minLength=lengthX;
		}
		
		//start addition
		int carry=0;
		String sum="";
		for(int i=0;i<maxLength;i++){
			int curr=carry+x.charAt(maxLength-i-1)-'0'+y.charAt(maxLength-i-1)-'0';
			if(curr>9){
				curr=curr-10;
				carry=1;
			}
			else
				carry=0;
			sum=curr+sum;
		}
		if(carry==1)
			sum=carry+sum;
		return sum;
	}
	public String bigIntegerMultiplication(String x, String y){
		boolean isNegative=false;
		if(x.charAt(0)=='-')
		{
			isNegative=!isNegative;
			x=x.substring(1, x.length());
		}
		if(y.charAt(0)=='-'){
			isNegative=!isNegative;
			y=y.substring(1, y.length());
		}
		
		String finalSum="";
		for(int i=0;i<y.length();i++){
			String sum="";
			int multiplier=y.charAt(y.length()-1-i)-'0';
			for(int j=0;j<multiplier;j++){
				 sum=bigIntegerAddition(sum,x);
			}
			for(int k=0;k<i;k++)
				sum=sum+'0';
			finalSum=bigIntegerAddition(finalSum,sum);
		}
		if(isNegative)
			finalSum='-'+finalSum;
		return finalSum;
	}
	
	public int[] rotate(int[] A, int index){
		if(index>A.length)
			return A;
		//reverse entire array
		for(int i=0;i<A.length/2;i++){
			int temp=A[i];
			A[i]=A[A.length-1-i];
			A[A.length-1-i]=temp;
		}
		for(int i=0;i<index/2;i++)
		{
			int temp=A[i];
			A[i]=A[index-1-i];
			A[index-1-i]=temp;
		}
		for(int i=index;i<(A.length+index)/2;i++)
		{
			int temp=A[i];
			A[i]=A[A.length+index-1-i];
			A[A.length+index-1-i]=temp;
		}
		/*for(int i=0;i<A.length;i++)
			System.out.println(A[i]);*/
		return A;		
	}
	
	public int findKthsmallestHelper(int[] a, int[] b, int k){
		A=new int[a.length];
		B=new int[b.length];
		A=a;
		B=b;
		return findKthsmallest(0, A.length-1 ,0, B.length-1,k);
	}
	public int findKthsmallest(int lowA, int highA ,int lowB, int highB,int k){
		//invariant k+1=i+j;
		int i=lowA+k/2;
		int j=k+1-i;
		
		int Ai_1 = (i<=0)?Integer.MIN_VALUE:A[i-1];
		int Bj_1=(j<=0)?Integer.MIN_VALUE:B[j-1];
		int Ai = (i<0)?Integer.MIN_VALUE:A[i];
		int Bj=(j<0)?Integer.MIN_VALUE:B[j];
		if(Ai_1<Bj && Bj<Ai)
			return Bj;
		else if(Bj_1<Ai && Ai<Bj)
			return Ai;
		
		if(Ai<Bj_1)
			return findKthsmallest(i,highA,lowB,j-1,k-i);
		else 
			return findKthsmallest(lowA,i-1,j,highB,k-j);
		
		
	}
	
	public int boardGameWin(int[] A){
		int[] P = new int[A.length];
		for(int i=0;i<A.length;i++)
			P[i]=0;
		for(int i=1;i<A.length;i++){
			int minstep=Integer.MAX_VALUE;
			for(int j=i-1;j>=0;j--){
				if(A[j]>=i-j && P[j]+1<minstep && P[j]!=0)
				{	P[i]=P[j]+1;
					minstep=P[i];
				}
			}
		}
		return P[A.length-1];
	}
	
	 private int partition(int l, int h,int pV){
        
         int low=l;
         int mid=l;
         int high=h;

         while(mid<=high){
                 if(arr[mid]==pV)
                         mid++;
                 else if(arr[mid]<pV){
                         swap(low,mid);
                         low++;mid++;
                 }
                 else{
                         swap(high,mid);
                         high--;
                 }
         }
        
         return low;
 }
	public int removeElement(int[] a, int k){
		int count=0;
		for(int i=0;i<a.length;i++)
			if(a[i]==Integer.MAX_VALUE)
				count++;
		arr=a;
		for(int i=0;i<arr.length;i++){
			if(arr[i]==k)
				arr[i]=Integer.MAX_VALUE;
		}
		int index = partition(0,arr.length-1,Integer.MAX_VALUE);
		return index+count;
	}
	
	public int removeDuplicates(int[] a)
	{
		int count=0;
		for(int i=0;i<a.length;i++)
			if(a[i]==Integer.MAX_VALUE)
				{
					count++;
					break;
				}
		
		arr=a;
		for(int i=0;i<arr.length;i++){
			int j=i+1;
			if(j>arr.length-1)
				break;
			while(arr[i]==arr[j]){
				arr[j]=Integer.MAX_VALUE;
				j++;
			}
			i=j-1;
		}
		int index = partition(0,arr.length-1,Integer.MAX_VALUE);
		return index+count;
	}
	
	/*
	 * Problem 6.11
	 */
	public int[] longestIncreasingSubArray(int[] a){
		int[] index=new int[2];
		int low=0;
		int high=0;
		int size=1;
		
		for(int i=1;i<a.length;i++){
			if(a[i]>a[i-1]){
				high++;
			}
			else{
				if(high-low>size){
					index[0]=low;
					index[1]=high;
					size=high-low;
				}
				low=i;
				high=i;
			}
		}
		return index;
	}
	/*
	 * Problem 6.12
	 * 
	 */
	public void findPrimes(int n){
		//get prime factors.
		int [] doors=new int[n];
		for(int j=0;j<n;j++)
			doors[j]=0;
		for(int gap=2;gap<=n;gap++){
			for(int i=gap-1;i<n;i=i+gap){
				doors[i]++;
			}
		}
		for(int i=0;i<n;i++)
			if(doors[i]==1)
				System.out.println(i+1);
		
	}
	/*
	 * Problem 6.13
	 */
	
	
	public int getProduct(int[] A, int value){
		int prod=1;
		for(int j=0;j<A.length;j++)
		{
			if(A[j]==value)continue;
			prod=prod*A[j];
		}
		return prod;
	}
	public int getLargestProduct(int[] A){
		int countZero=0;
		int countNeg=0;
		int countPos=0;
		for(int i=0;i<A.length;i++){
			if(A[i]==0)
				countZero++;
			else if(A[i]>0)
				countPos++;
			else
				countNeg++;
		}
		
		if(countZero>1 || (countZero==1 && countNeg>0))
			return 0;
		if(countZero==1 && countNeg==0){
			return getProduct(A,0);
		}
		if(countNeg%2==0){
			int min=Integer.MAX_VALUE;
			for(int j=0;j<A.length;j++){
				if(A[j]<min && A[j]>0)
					min=A[j];
			}
			return getProduct(A, min);
		}
		else{
			int max=Integer.MIN_VALUE;
			for(int j=0;j<A.length;j++){
				if(A[j]>max && A[j]<0)
					max=A[j];
			}
			return getProduct(A, max);
		}
	}
	
	public  void swap(char[] array, int i, int j){
		char temp=array[i];
		array[i]=array[j];
		array[j]=temp;
	}
	private void swap(int[] array, int i, int j) {
		int temp=array[i];
		array[i]=array[j];
		array[j]=temp;

	}
	public void permute(char[] input, int[] rule){
		int prev=0;
		int curr=rule[prev];
		int itr=0;

		while(itr<input.length){
			if(prev==curr){
				prev=itr;
				curr=rule[prev];
			}
			swap(input, prev,curr);
			swap(rule,prev,curr);
			curr=rule[prev];
			itr++;
		}
	}

	public int[] maxProfit(int[] A,int i, int j){
		int[] arr=new int[j-i+1];
		int minval=A[i];
		int maxProfit=A[i+1]-A[i];

		for(int k=i+1;k<=j;k++){
			if(A[k]-minval>maxProfit)
				maxProfit=A[k]-minval;
			if(A[k]<minval)
				minval=A[k];
			arr[k-i]=maxProfit;
		}
		return arr;
	}

	public int[][] generateProfitArray(int[] A){
		int[][] profit=new int[A.length][A.length];
		for(int i=0;i<A.length-1;i++){
			int[] p=maxProfit(A,i,A.length-1);
			for(int k=i;k<A.length;k++)
				profit[i][k]=p[k-i];
		}
		System.out.println("done");
		return profit;
	}

	public int getMaxProfitKtries(int[] A, int K){
		int[][] profit=generateProfitArray(A);
		return getMaxProfitKtries(A,profit,0,A.length-1,K);
	}

	
	
	public int getMaxProfitKtries(int[] A, int[][] profit,int left, int right,int K){
		int maxPr=0;
		
		if(K==1)
			return profit[left][right];
		else{
			for(int i=left+1;i<right;i++){
				if(i-left>=K-1 && right-i>=1)
				{
					int pr=getMaxProfitKtries(A,profit,left,i,K-1)+getMaxProfitKtries(A,profit,i,right,1);
					if(pr>maxPr)
						maxPr=pr;
				}
			}
		}
		System.out.println(maxPr);
		return maxPr;
	}
	
	public int getMaxProfitKtriesDP(int[] A, int K){
		int[][] profit=generateProfitArray(A);
		return getMaxProfitKtriesDP(A,profit,K);
	}
	public int getMaxProfitKtriesDP(int[] A, int[][] profit,int K){
		int maxPr=0;
		int n=A.length;
		int[][] T=new int[n][K];
		
		for(int i=0;i<n;i++)
			T[i][0]=profit[0][i];
	
		for(int i=1;i<n;i++){
			for(int k=1;k<K;k++){
				maxPr=0;
				/*if(k-1>=i)
					continue;*/
				for(int j=k-1;j<=i-1;j++){
					int pr=T[j][k-1]+profit[j][i];
					if(pr>maxPr)
						maxPr=pr;
				}
				T[i][k]=maxPr;
			}
		}
		System.out.println(T[n-1][K-1]);
		return T[n-1][K-1];
	}
	
	public int getTimeComplexity(int n, int k){
		int[][] T=new int[n][k];
		
		for(int i=0;i<n;i++)
			T[i][0]=1;
		
		for(int j=1;j<k;j++)
			for(int i=0;i<n;i++){
				for(int p=j-1;p<i;p++){
					T[i][j]=T[i][j]+T[p][j-1];
				}
				T[i][j]=T[i][j]+i-j+1;
					
			}
		return T[n-1][k-1];
	}

}
